import java.util.ArrayList;

/**
 * Recursively parses a regular expression and uses the syntax tree to create an NFA.  Uses
 * a stack to maintain NFA data during recursion.
 * @author Trevor Radcliffe
 *
 */
public class RegexParser{
	
	//NFA to match all uppercase for rule finding defined class names
	NFA ruleMatch = new NFA("[A-Z]+", 'A', 'Z', '+');
	
	ScannerGenerator sg;
	
	String[] RE_CHAR = new String[127];
	String[] CLS_CHAR = new String[127];	
	//Current string being processed
	String input = "";
	//Index of the character being processed
	int charIndex = -1;
	//The character being processed
	char current = ' ';
	//The NFA being built
	NFAStack nfaStack = new NFAStack();

	public RegexParser(String s, ScannerGenerator sg){
		
		//RE_CHAR and CLS CHAR; printable characters go from 32-126
		String rexpEscape = " \\*+?|[]().'\"";
		String clsEscape = "\\^-[]";
		for(int i=32; i<=126; i++){
				RE_CHAR[i]= ((rexpEscape.indexOf(i)>0)?"\\":"") + (char)i;
				CLS_CHAR[i]= ((clsEscape.indexOf(i)>0)?"\\":"") + (char)i;
//				System.out.println(RE_CHAR[i] + "\n"+ CLS_CHAR[i]);
		}
		input=s;
		this.sg=sg;
		
	}

	//Testing main method--Comment out for actual use.
	public static void main(String[] args)
	{
		/*
		RegexParser cc1 = new RegexParser("[^n-p] IN [a-z]");
		NFA nc1 = cc1.parse();
		nc1.cloneNFA(true);*/
	}
	/*
	 * Creates an NFA for recognizing a given regular expression.
 	 * @param s The string to parse into an NFA
	 * @return An NFA that will recognize the given regular expressin
	 */
	NFA parse()
	{
		try{
			regEx();
			
			reset();
			NFA a = nfaStack.pop();
			if(!a.name.equals("empty"))
				return a;
			return NFA.emptyNFA();

		} catch(MalformedRegexException e){
			e.complain();
			return NFA.emptyNFA();
		}
	}
	
	/**
	 * Resets the RegexParser
	 */
	void reset(){
		charIndex=-1;
		current=' ';
	}
	
	/**
	* @param s The character that is being tested against the current input
	* @return True if the current character matches s
	*/ 	
	boolean expect(char s) throws MalformedRegexException
	{
		//System.out.println(current);
		
		if(current==s)
		{
			getNext();
			return true;
		}
		//System.out.println("Unexpected Character: "+s);
		return false;
	}

	
	/**
	 * Check to see if the expected character is within a set of 
	 * characters.
	 * @param s The set of characters (strings to allow for escape sequences
	 * @return The index in the array of the character that matched if any did, -1 if not
	 * @throws MalformedRegexException 
	 */
	int expect(String[] s) throws MalformedRegexException
	{
		//Do not use get next in order to handle white space
		for(int i=32; i<=126; i++){
			if(!peek('\\')){
				if(peek(s[i].charAt(0))){
					charIndex++;
					if(charIndex<input.length())
						current=input.charAt(charIndex);
					else
						current='\0';
					return i;
				}
			}
			else if(s[i].charAt(0)=='\\'){
				if(input.length()>charIndex+1 && s[i].charAt(1)==input.charAt(charIndex+1)){
					charIndex+=2;
					if(charIndex<input.length())
						current=input.charAt(charIndex);
					else
						current='\0';
					return i;				
				}
			}
			
		}
		return -1;
	}
	
	/**
	 * Checks the input for a given string of characters,
	 * one at a time.
	 * @param s The string to be checked
	 * @return -1 if the string was expected, the index of the unexpected character otherwise.
	 * @throws MalformedRegexException 
	 */
	int expect(String s) throws MalformedRegexException{
		for(int i =0; i<s.length(); i++)
		{
			if(!expect(s.charAt(i)))
					return i;
		}
		return -1;
	}
	
	/**
	 * Looks at the currently being processed character without removing it.
	 * @param c Character to be compared to the current
	 * @return True if current is equal to c, false otherwise
	 */
	boolean peek(char c){
		if(current=='\0')
			return false;
		if(current==c)
			return true;
		return false;
	}
	
	
	/**
	 * Checks a list of characters (Strings for escape characters)
	 * for being at the current character without removing it.
	 * @param s Array of strings containing characters to be compared
	 * @return The index of the character that matched if there was one, -1 otherwise
	 * @throws MalformedRegexException 
	 */
	int peek(String[] s) throws MalformedRegexException{

		for(int i=32; i<=126; i++){
			if(!peek('\\')){
				if(peek(s[i].charAt(0)))
					return i;
			}else if(s[i].charAt(0)=='\\'){
				if(input.length()>charIndex+1 && s[i].charAt(1)==input.charAt(charIndex+1))
					return i;
			}
		}
		return -1;
		}

	/**
	 * Increments charIndex to get the next character of the input, ignoring whitespace.
	 * @return The new current character
	 */
	char getNext()
	{
		do{
			if(charIndex>=input.length()-1)
			{
				charIndex=input.length();
				current='\0';
				return '\0';
			}
			charIndex++;
			current = input.charAt(charIndex);
		}while(current == ' ' || current == '\n' || current == '\r'
				|| current == '\f' || current == '\t');
		return input.charAt(charIndex);
	}
/*--------------------------------------------------------------------------------
 * Recursive parsing methods
 *--------------------------------------------------------------------------------
 */
	void regEx() throws MalformedRegexException
	{
		if(getNext()!='\0'){
			rexp();
			if(current!='\0')
				throw new MalformedRegexException(input);
		}else{
			System.out.println("The input was the empty string");
		}
	}

	void rexp() throws MalformedRegexException
	{
		rexp1(); 
		rexpPrime();
	}
	
	void rexpPrime() throws MalformedRegexException
	{
		if(expect('|')){
			if(peek(')') || charIndex>=input.length())
				nfaStack.push(NFA.emptyNFA());
			else{
				rexp1(); 
				rexpPrime();
			}
			NFA a = nfaStack.pop();
			NFA b = nfaStack.pop();
			if(b.name.equals("blank"))
				throw new MalformedRegexException(input);
			if(!a.name.equals("blank"))
				b.union(a);
			nfaStack.push(b);
		}
	}

	void rexp1() throws MalformedRegexException
	{
		
		rexp2();

		rexp1Prime();
		
	}

	void rexp1Prime() throws MalformedRegexException
	{
		//Check follow set
		if(peek('(') || peek(RE_CHAR) >0 || peek('.') || peek('[') || peek('$')){

			rexp2();
			
			rexp1Prime();
			NFA a = nfaStack.pop();
			NFA b = nfaStack.pop();
			
			if(b.name.equals("empty"))
				throw new MalformedRegexException(input);
			
			if(!a.name.equals("empty"))
				b.concat(a);
			nfaStack.push(b);
			
		}
	}

	void rexp2() throws MalformedRegexException
	{
		if(expect('(')){
			rexp();
			if(expect(')'))
				;
			else
				throw new MalformedRegexException(input);
			rexp2Tail();
			return;
		}


		rexp3();
		//Index of character that matched, if there is one
		int match= expect(RE_CHAR);

		if(match>=0){
			rexp2Tail();
			char character = RE_CHAR[match].charAt(RE_CHAR[match].charAt(0)=='\\'?1:0);
			nfaStack.push(new NFA(""+character, character, character, ' '));
			return;
		}


	}
	
	void rexp2Tail() throws MalformedRegexException
	{

		NFA a = nfaStack.pop();
		if(expect('*'))
		{
			a.star();
		}else if(expect('+')){
			a.plus();
		}

		if(!a.name.equals("empty"))
			nfaStack.push(a);
	}

	void rexp3() throws MalformedRegexException
	{
		charClass();
	}

	void charClass() throws MalformedRegexException
	{
		
		if(expect('.'))
		{
			nfaStack.push(new NFA(".", 1, 255, ' '));
			return;
		}
		if(peek('['))
		{
			//Don't use getNext() because of whitespace
			charIndex++;
			if(charIndex<input.length())
				current=input.charAt(charIndex);
			else
				throw new MalformedRegexException(input);
			charClass1();
			return;
		}
			definedClass();
	}

	void charClass1() throws MalformedRegexException
	{
		if(current=='^'){
			excludeSet();
			return;
		}
		//Counteract extra pop in CharSetList()
		nfaStack.push(NFA.blankNFA());
		
		charSetList();
	}

	void charSetList() throws MalformedRegexException
	{
		if(expect(']')){
			return;
		}
		if(peek(CLS_CHAR)<0)
				throw new MalformedRegexException(input);
		
		String bounds = charSet();
		
		charSetList();
		NFA a;
		if(bounds.charAt(1)!='\0')
			a = new NFA("["+bounds.charAt(0)+"-"+bounds.charAt(1)+"]", bounds.charAt(0), bounds.charAt(1), ' ');
		else
			a = new NFA("["+bounds.charAt(0)+"-"+bounds.charAt(1)+"]", bounds.charAt(0), bounds.charAt(0), ' ');
		a.union(nfaStack.pop());
		nfaStack.push(a);
	}

	String charSet() throws MalformedRegexException
	{
		//index of match, if it exists
		int match=expect(CLS_CHAR);
		if(match>=0)
		{
			return ""+(char)match+charSetTail();
		}
		
		throw new MalformedRegexException(input);
	}

	char charSetTail() throws MalformedRegexException
	{
		//Index of match, if it exists
		if(!expect('-'))
			return '\0';
		int match = expect(CLS_CHAR);
		if(match>=0)
		{
			return (char)match;
		}else{
			throw new MalformedRegexException(input);
		}
	}

	void excludeSet() throws MalformedRegexException
	{
		if(expect('^')){
				String bounds=charSet();
			if(expect("]IN")==-1){
				excludeSetTail();
				NFA a =nfaStack.pop();
				char start = bounds.charAt(0);
				char end;
				if(bounds.charAt(1)!='\0')
					end = bounds.charAt(1);
				else
					end = bounds.charAt(0);
				nfaStack.push(new NFA("[^"+start+"-"+end+"] IN "+ a.name, start, end, '\0',a , true));
				return;
			}
		}
		throw new MalformedRegexException(input);
	}

	void excludeSetTail() throws MalformedRegexException
	{
		if(expect('['))
		{
			 String bounds = charSet();
			 if(expect(']')){
				 char start = bounds.charAt(0);
				 char end = bounds.charAt(1);
				 if(end!='\0')
					 nfaStack.push(new NFA("["+start+ "-" + end+"]", start, end, ' '));
				 else
					 nfaStack.push(new NFA("["+start+ "-" + end+"]", start, start, ' '));
				 return;
			 }
			 throw new MalformedRegexException(input);
		}
		definedClass();
	}

	void definedClass() throws MalformedRegexException
	{
		if(expect('$')){		
			String rule = "$";
			while(ruleMatch.match(""+current)){
				rule+=current;
				getNext();
			}
			if(sg.getRule(rule)!=null){
				nfaStack.push(sg.getRule(rule).getNFA());
			}else
				throw new MalformedRegexException(input);
		}
	}
	
	/**
	 * Special exception that knows how to throw a fit when 
	 * you give it an incorrect regex
	 * @author Trevor Radcliffe
	 *
	 */
	@SuppressWarnings("serial")
	private class MalformedRegexException extends Exception{
		String regex="";
		private MalformedRegexException(String regex){
			this.regex=regex;
		}
		
		void complain(){
			System.out.println("Malformed Regex: " + regex);
		}
	}
	
	/**
	 * A stack of NFAs used for combining NFAs.
	 * @author Trevor Radcliffe
	 *
	 */
	private class NFAStack{
		ArrayList<NFA> stack;
		
		public NFAStack(){
			stack=new ArrayList<NFA>();
		}
		
		public void push(NFA nfa){
			stack.add(nfa);
		}
		public NFA pop(){
			try{
				return stack.remove(stack.size()-1);
			}catch(ArrayIndexOutOfBoundsException e){
				return NFA.emptyNFA();
			}
		}
		
		@SuppressWarnings("unused")
		public NFA peek(){
			try{
				return stack.get(stack.size()-1);
			}catch(ArrayIndexOutOfBoundsException e){
				return NFA.emptyNFA();
			}
		}
	}
}
